package org.example.myleet.p454;

import java.util.HashMap;
import java.util.Map;

/**
 * HashMap存两个数组之和，如AB。然后计算两个数组之和，如 CD。时间复杂度为：O(n^2)+O(n^2)，得到 O(n^2)
 * 两个双重循环比一个四重循环要少两个指数级复杂度
 * 其实还是有一点点DP的味道，只不过DP只能帮助到中间位置，再往前的话可能性太多，或者称为双向DP
 */
public class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> possibleAnswers = new HashMap<>();
        int t;
        for (int i=0; i<D.length; i++) {
            for (int j=0; j<C.length; j++) {
                t = -(D[i] + C[j]);
                if (possibleAnswers.containsKey(t)) {
                    possibleAnswers.put(t, possibleAnswers.get(t) + 1);
                } else {
                    possibleAnswers.put(t, 1);
                }
            }
        }
        int count = 0;
        for (int i=0; i<A.length; i++) {
            for (int j=0; j<B.length; j++) {
                t = A[i] + B[j];
                if (possibleAnswers.containsKey(t)) {
                    count += possibleAnswers.get(t);
                }
            }
        }
        return count;
    }
}
